package demo;

public class P42 {

    public static void main(String[] args) {
        int[] a = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
        P42 p42 = new P42();
        System.out.println(p42.trap2(a));
    }

    public int trap(int[] hs) {
        int maxL = 0;
        int count = 0;

        for (int i = 1; i < hs.length; i++) {
            maxL = Math.max(maxL, hs[i - 1]);
            int maxR = 0;
            for (int j = i + 1; j < hs.length; j++) {
                maxR = Math.max(maxR, hs[j]);
            }
            if (Math.min(maxL, maxR) - hs[i] > 0)
                count += Math.min(maxL, maxR) - hs[i];
        }
        return count;
    }


    public int trap2(int[] hs) {

        int[] maxLs = new int[hs.length];
        int[] maxRs = new int[hs.length];


        int count = 0;
        int maxL = 0;
        int maxR = 0;
        for (int i = 1; i < hs.length; i++) {
            maxL = Math.max(maxL, hs[i - 1]);
            maxLs[i] = maxL;
        }

        for(int i=hs.length-1-1;i>=0;i--){
            maxR= Math.max(maxR,hs[i+1]);
            maxRs[i]=maxR;
        }

        for (int i = 0; i < maxRs.length; i++) {
            if (Math.min(maxLs[i], maxRs[i]) - hs[i] > 0)
                count += Math.min(maxLs[i], maxRs[i]) - hs[i];
        }

        return count;
    }


}
